package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-16 08:40:23
 */
class Q0074_SearchA2dMatrix {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int row = matrix.length;
            int col = matrix[0].length;
            for (int i = 0; i < row; i++) {
                if (matrix[i][0] == target || matrix[i][col - 1] == target) {
                    return true;
                }

                if (matrix[i][0] < target && matrix[i][col - 1] > target) {
                    if (Math.abs(matrix[i][0] - target) <= Math.abs(matrix[i][col - 1] - target)) {
                        for (int j = 1; j < col; j++) {
                            if (target == matrix[i][j]) return true;
                        }
                    } else {
                        for (int j = col - 1; j > 0; j--) {
                            if (target == matrix[i][j]) return true;
                        }
                    }
                    break;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0074_SearchA2dMatrix().new Solution();
        System.out.println(solution.searchMatrix(new int[][]{
                {1, 3, 5}
        }, 3));
        System.out.println(solution.searchMatrix(new int[][]{
                {1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}
        }, 3));
        System.out.println(solution.searchMatrix(new int[][]{
                {1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}
        }, 13));
    }
}